/*
 * @lc app=leetcode.cn id=381 lang=javascript
 *
 * [381] O(1) 时间插入、删除和获取随机元素 - 允许重复
 */

// @lc code=start
/**
 * Initialize your data structure here.
 */
var RandomizedCollection = function () {
  /**
   * @type {Map<Number, Set>}
   */
  this.index = new Map();
  /**
   * @type {Number[]}
   */
  this.values = [];
};

/**
 * Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function (val) {
  this.values.push(val);
  /**
   * @type {Set<number>}
   */
  const set = this.index.has(val) ? this.index.get(val) : new Set();
  set.add(this.values.length - 1);
  this.index.set(val, set);
  return set.size === 1;
};

/**
 * Removes a value from the collection. Returns true if the collection contained the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function (val) {
  if (!this.index.has(val)) {
    return false;
  }

  let idx = -1;
  for (const index of this.index.get(val)) {
    if (idx === -1) {
      idx = index;
      break;
    }
  }

  const lastValue = this.values[this.values.length - 1];
  this.values[idx] = lastValue;

  this.index.get(val).delete(idx);
  this.index.get(lastValue).delete(this.values.length - 1);

  idx < this.values.length - 1 && this.index.get(lastValue).add(idx);

  this.index.get(val).size === 0 && this.index.delete(val);

  this.values.pop();

  return true;
};

/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function () {
  const size = this.values.length;
  return this.values[Math.floor(Math.random() * size)];
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
// @lc code=end

/**
 * 时间复杂度：O(1)
 * 空间复杂度：O(N)，其中 N 为集合中的元素数目
 */
